package 集合.hashCode与equals;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

import 函数式编程.使用Stream.Student;
/*
public class 编写equals {
   public static void main(String[] args) {
       List<Person> list = Arrays.asList(
           new Person("Xiao", "Ming", 18),
           new Person("Xiao", "Hong", 25),
           new Person("Bob", "Smith", 20)
       );
       boolean exist = list.contains(new Person("Bob", "Smith", 20));
       System.out.println(exist ? "测试成功!" : "测试失败!");
   }
}

class Person {
   String firstName;
   String lastName;
   int age;
   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
//   public boolean equals(Object o) {
//      if (o instanceof Person) {
//          boolean nameEquals = false;
//          Person p=(Person) o;
//          if ((this.firstName == null && p.firstName == null)&&(this.lastName == null && p.lastName == null)){
//              nameEquals = true;
//          }
//          if ((this.firstName != null) && (this.lastName != null)) {
//              nameEquals = this.firstName.equals(p.firstName) && this.lastName.equals(p.lastName);
//          }
//          return nameEquals && this.age == p.age;
//      }
//      return false;
//  }
   public boolean equals(Object o) {
   	//if (o instanceof Person) {
   	//	Person p = (Person) o;
   	//	return Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName) && (this.age==p.age);
   	//}
   	//return false;
   	
   	//Java14之后对instanceof进行了升级，不仅仅是直接用来进行类型匹配，还可以直接(o)转换成相应的实例(p)。即：o --> (Person) p
		if (o instanceof Person p) {//将o转成Person p
         return Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName) && (this.age==p.age);
      }
      return false;
   }
}
*/
/*
Object中的hashCode()
hashCode方法用来返回对象的哈希值，提供该方法是为了支持哈希表，例如HashMap，HashTable等，在Object类中的代码如下:

 public native int hashCode();
这是一个native声明的本地方法，返回一个int型的整数。由于在Object中，因此每个对象都有一个默认的哈希值。

在openjdk8根路径/hotspot/src/share/vm/runtime路径下的synchronizer.cpp文件中,有生成哈希值的代码：

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // 返回随机数
     value = os::random() ;
  } else
  if (hashCode == 1) {
     //用对象的内存地址根据某种算法进行计算
     intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     // 始终返回1，用于测试
     value = 1 ;            
  } else
  if (hashCode == 3) {
     //从0开始计算哈希值
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     //输出对象的内存地址
     value = cast_from_oop<intptr_t>(obj) ;
  } else {
     // 默认的hashCode生成算法，利用xor-shift算法产生伪随机数
     unsigned t = Self->_hashStateX ;
     t ^= (t << 11) ;
     Self->_hashStateX = Self->_hashStateY ;
     Self->_hashStateY = Self->_hashStateZ ;
     Self->_hashStateZ = Self->_hashStateW ;
     unsigned v = Self->_hashStateW ;
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
     Self->_hashStateW = v ;
     value = v ;
  }

  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

源码中的hashCode其实是JVM启动的一个参数，每一个分支对应一个生成策略，通过-XX:hashCode可以切换hashCode的生成策略。
下面验证第2种生成策略，用软件idea输入参数-XX:hashCode=2，可以看到输出结果正是1，从而进一步验证了上面的源码。




hashCode()和equals()
hashCode()和equals()用来标识对象，两个方法协同工作用来判断两个对象是否相等。对象通过调用 Object.hashCode（）生成哈希值，由于不可避免地会存在哈希值冲突的情况 因此hashCode 相同时 还需要再调用 equals 进行一次值的比较，但是若hashCode不同，将直接判定两个对象不同，跳过 equals ，这加快了冲突处理效率。 Object 类定义中对 hashCode和 equals 要求如下:

如果两个对象的equals的结果是相等的，则两个对象的 hashCode 的返回结果也必须是相同的。
任何时候重写equals，都必须同时重写hashCode。
下面看一个小例子:

import java.util.HashMap;
import java.util.Objects;


public class Person {
    //用户Id，唯一确定用户
    private String id;
    private String name;

    public Person(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id) && Objects.equals(name, person.name);
    }

		//Java14之后对instanceof进行了升级，不仅仅是直接用来进行类型匹配，还可以直接(o)转换成相应的实例(p)。即：o --> (Person) p
		if (o instanceof Person p) {//将o转成Person p
         return Objects.equals(this.id,p.id) && Objects.equals(this.name,p.name);
      }
      return false;


    public static void main(String[] args) {
        HashMap<Person, Integer> map = new HashMap<>();
        //key:Person类型  value:Integer类型
        map.put(new Person("1","张三"),100);
        System.out.println(map.get(new Person("1", "张三")));
    }
}

我们将Person类的实例作为key，value为这个对象的考试成绩。我们期望通过map.get(new Person("1", "张三"))获取该对象的考试成绩，但上面代码的输出结果为null。原因就
在于Person类中没有覆盖hashCode方法，从而导致两个相等的实例具有不同的哈希值。HashMap中get()的核心代码如下

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
     return first;


if条件表达式中的e.hash == hash是先决条件，只有相等才会执行&&后面的代码。equals不相等时并不强制要求哈希值相等，但是一个优秀的哈希算法应尽可能让元素均匀分布，降低
冲突发生的概率，即在equals不相等时尽量让哈希值也不相等，这样&&或||短路操作一旦生效，会极大提高程序的效率。像上面的例子，因为没有重写hashCode方法，两个对象有两个哈
希值，获取对象时可能在别的哈希桶中查找，即使凑巧在一个哈希桶，因为哈希值不一样，也找不到原来那一个对象。
你可以根据你自己的需求设计重写hashCode方法，或者调用JDK提供好的，比如

  @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

这样就能解决问题，但是这个运行速度慢一些，因为它们会引发数组的创建，以便传入数目可变的参数， 如果参数中有基本类型，还需要装箱和拆箱 ，建议只将这类散列函数用于不太注重性能
的情况。

重写的hashCode()方法
Java为许多常用的数据类型重写了hashCode()方法，比如String，Integer，Double等。比如在Integer类中哈希值就是其int类型的数据。

  public static int hashCode(int value) {
        return value;
    }




1.Hash概述
Hash称为“散列”或者音译“哈希”，本质上是一种压缩映射，也就是说把任意长度的消息，通过散列算法压缩成某一固定长度的消息，由于散列的空间通常远小于输入的空间，因此不同的输
入可能会散列出相同的输出。

2.hashCode的作用
hashCode方法返回一个hash code值，这个方法是为了更好的支持hash表，例如：HashMap、HashTable等，
在使用hash表这类数据结构时，首先需要通过hash函数计算出一个hash值，然后根据这hash值,放入到对应的Hash表对应的Key上,如果不同的对象确产生了相同的hash值,也就是
发生了Hash值相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hash值的对象放到这个单链表上去,串在一起。

数组    链表
┌───┐
│   │   ┌───┐  ┌───┐
│ 0 ├───┤ c ├──┤ f │
│   │   └───┘  └───┘
├───┤            
│   │   ┌───┐  ┌───┐
│ 1 ├───┤ a ├──┤ d │
│   │   └───┘  └───┘
├───┤            
│   │   ┌───┐  ┌───┐
│ 2 ├───┤ b ├──┤ e │
│   │   └───┘  └───┘
└───┘

查找某个对象时,首先会计算出要查询对象的hash值，通过hash值确定该对象在哪个链表中，然后用equals方法依次判断该对象和链表上的对象是否相等。

-提高了对象的查询效率，只有在发生了hash冲突的情况下，才需要通过线性查找对象。
-如果两个对象相同，那么它们的hash值一定相同；如果两个对象的hash值相同，并不一定表示两个对象相同，但他们一定在同一个链表上。

Tips:
 · hashCode方法返回一个32位的int整数，hash值的取值范围是： -2^31 ~ 2^31 -1 ，因此若存在 2^32 + 1个对象，那么一定会有两个不同的对象有一样的hash值。
 · Object.hashCode返回的hash值不是对象内存地址。

3.为什么重写equals的同时还得重写hashCode（重点）
因为如果你只重写了equals方法而没有重写hashCode方法，那么在使用散列这样的数据结构时，没办法处理好你的键。这事实上违反了Object hashCode通约的第二条。

java.lnag.Object中对hashCode通约：

	1）在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。
	2）如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
	3）如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。

下面举出了一个只重写了equals方法的例子：

import java.util.HashMap;
import java.util.Map;
*/
public class 编写equals {

    public static void main(String[] args) {

        Map<Key, Integer> map = new HashMap<Key, Integer>();
        Key k1 = new Key(123L);
        Key k2 = new Key(123L);
        map.put(k1, 2);
        System.out.println("map.get(k1):" + map.get(k1));//2
        System.out.println("map.get(k2):" + map.get(k2));//null
        System.out.println("k1.equals(k2):" + k1.equals(k2));
        System.out.println("k1.hashCode:" + k1.hashCode());
        System.out.println("k2.hashCode:" + k2.hashCode());
    }

}

class Key {
    private Long k;
    //private String k;

    public Key(Long key) {
        this.k = key;
    }


    @Override
    public int hashCode() {
   	 return Objects.hash(k);
    }
    //public static int hash(Object... values) {
    //   return Arrays.hashCode(values);
    //}
    //Arrays类方法：参数类型自动判定，可以是以下类型：
    //hashCode(long[])
    //hashCode(int[])
    //hashCode(short[])
    //hashCode(char[])
    //hashCode(byte[])
    //hashCode(boolean[])
    //hashCode(float[])
    //hashCode(double[])
    //hashCode(Object[])
    
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        
        Key key = (Key) o;
        
        return k != null ? k.equals(key.k) : key.k == null;
    }
    
}
/*
输出：
map.get(k1):2
map.get(k2):null
k1.equals(k2):true
k1.hashCode:21685669
k2.hashCode:2133927002

解析：
可以看到，k1和k2是等价的，但map.get(k2)并没有拿到我们想要取得的对象，因为Key并没有去重写hashCode方法，所以k1、k2的hash值是不一样的，所以以k2的hash值是
无法正确找到k1 hash值所对应值的。这也说明了，如果你只实现equals方法而没有实现hashCode方法，那么将会给你在使用散列这类数据结构时埋下隐患！

原因在于没有覆盖hashCode方法，从而导致两个相等的实例具有不同的哈希值。HashMap中get()的核心代码如下
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
     return first;
if条件表达式中的e.hash == hash是先决条件，只有相等才会执行&&后面的代码。所以因为hash值不同，判断为：不是相同对象

4.hashCode的实现
1.把某个非0的常数值，比如17，保存在一个名为result的int类型的变量中。

2.对于对象中的每个域，做如下操作：

  a.为该域计算int类型的哈希值c：

	·如果该域是boolean类型，则计算(f?1:0)
	·如果该域是byte、char、short或者int类型，则计算(int)f
	·如果该域是long类型，则计算(int)(f^(f>>>32))
	·如果该域是float类型，则计算Float.floatToIntBits(f)
	·如果该域是double类型，则计算Double.doubleToLongBits(f)，然后重复第三个步骤。
	·如果该域是一个对象引用，并且该类的equals方法通过递归调用equals方法来比较这个域，同样为这个域递归的调用hashCode，如果这个域为null，则返回0。
	·如果该域是数组，则要把每一个元素当作单独的域来处理，递归的运用上述规则，如果数组域中的每个元素都很重要，那么可以使用Arrays.hashCode方法。

  b.把上面计算得到的hash值c 按照result = 31*result + c 公式 加入到result中

3.返回result

示例代码：

import java.util.Arrays;

public class HashCodeExample {

    private boolean flag;
    private int num;
    private long longNum;
    private double doubleNum;
    private int[] ids;
    private Student student;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        HashCodeExample that = (HashCodeExample) o;

        if (flag != that.flag) return false;
        if (num != that.num) return false;
        if (longNum != that.longNum) return false;
        if (Double.compare(that.doubleNum, doubleNum) != 0) return false;
        if (!Arrays.equals(ids, that.ids)) return false;
        return student != null ? student.equals(that.student) : that.student == null;
    }

    @Override
    public int hashCode() {
        int result;
        long temp;
        //boolean
        result = (flag ? 1 : 0);
        //int
        result = 31 * result + num;
        //long
        result = 31 * result + (int) (longNum ^ (longNum >>> 32));
        //double
        temp = Double.doubleToLongBits(doubleNum);
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        //数组
        result = 31 * result + Arrays.hashCode(ids);
        //引用
        result = 31 * result + (student != null ? student.hashCode() : 0);
        return result;
    }
}

class Student{
    private int id;
    private String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Student student = (Student) o;

        if (id != student.id) return false;
        return name != null ? name.equals(student.name) : student.name == null;
    }

    @Override
    public int hashCode() {
        int result = id;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        return result;
    }
}

Tips：

计算hash值时必须排除equals比较时没有用到的域，否则可能会违反Object.hashCode通约的第二条。
31是个奇素数，而且31的乘法可以用移位和减法替代：31* i == ( i << 5 ) - i ，JVM会自动优化。
hashCode和equals方法都可以用开发工具的快捷键生成的。
*/